package features.advance.edu.algorithm.chapt2_3;

/**
 * 一个已排序的序列A，和给定数字v，采用二分法找出v在序列中的位置下标，如果不存在，就返回-1
 * 时间复杂度都是O(lgN)
 * @author LIN
 * @date 2021-08-05
 */
public class Execise2_3_5 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
        };
        int[] arr = {1,2,3,4,5,6};
        int v = 6;
        int index = solution.searchviteration(arr, v);
        int index1 = solution.searchvrecursion(arr, v);
        System.out.println(index);

    }

    static class Solution {

        /**
         * 递归法查找指定元素下标
         * @param arr
         * @param v
         * @return
         */
        public int searchvrecursion(int[] arr, int v){
            int left = 0;
            int right = arr.length-1;
            return recursion(left,right,arr,v);
        }

        /**
         * 二分查找
         * @param left
         * @param right
         * @param arr
         * @param v
         * @return v的元素下标
         */
        public int recursion(int left,int right,int[] arr,int v){
            if(left > right){
                return -1;
            }
            int midLen = (left+right)/2;
            if(arr[midLen] == v){
                return midLen;
            }else if(arr[midLen] < v){
                return recursion(left+1,right,arr,v);
            }else {
                return recursion(left,right-1,arr,v);
            }
        }

        /**
         * 使用迭代法查找指定元素下标
         * @param arr
         * @return
         */
        public int searchviteration(int[] arr, int v){
            if(arr == null || arr.length == 0){
                return -1;
            }
            int length = arr.length;
            int left = 0;
            int right = length-1;
            while(left <= right){
                int midLen = (left + right)/2;
                if(arr[midLen] == v){
                    return midLen;
                }else if(arr[midLen] < v){
                    left = midLen+1;
                }else {
                    right = midLen-1;
                }
            }
            return -1;
        }
    }
}
